package com.culture.bootdemo.算法.sort;

import java.util.Arrays;

/**
 * @author: wen
 * @date 2020/10/23
 * 快速排序：基于分治法
 * <p>
 * 原理：通过一次划分将待排序数组分成两个子数组：左子数组的所有元素都小于基准值，右子数组的所有元素都大于基准值。
 * 然后递归地对两个子数组分别进行快速排序，最终完成整个数组的排序
 * 当子数组的长度为 0 或 1 时，直接返回（无需再排序）
 * <p>
 * 时间复杂度: 平均情况是O(nlog(n)),最差情况是O(n^2),即冒泡排序复杂度<br>
 * 空间复杂度: O(nlog(n))
 */
public class KuaiSuSort {


    // 主方法：用于调用快速排序方法
    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }

    // 快速排序的核心方法
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 哨兵划分 获取划分点，基准元素归位的位置
        int partitionIndex = partition(arr, left, right);

        // 递归左子数组、右子数组（以基准元素划分左右子数组）
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);

    }

    /**
     * 找出一个基准点，排列数组array左边的都小于它，右边的都大于它
     *
     * @param arr
     * @param left
     * @param right
     * @return 基准值数组索引
     */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 选择最右边的元素作为基准
        int i = left - 1; // 指针i指向小于基准的最后一个元素的位置

        for (int j = left; j < right; j++) {
            // 如果当前元素小于等于基准元素，将其与指针i的下一个元素交换
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准元素放到指针i的下一个位置（即基准的正确位置）
        swap(arr, i + 1, right);
        return i + 1; // 返回基准元素的位置
    }

    // 哨兵划分: 以 nums[right] 为基准数
    public static int partition2(int[] nums, int left, int right) {
        // 以 nums[right] 为基准数
        int pivot = nums[right];  // 基准值
        int i = left, j = right - 1; // 左右指针，注意 j 初始化为 right - 1

        while (i <= j) { // 循环直到 i 和 j 相遇
            while (i <= j && nums[i] <= pivot)
                i++;  // 从左向右找首个大于基准值的元素
            while (i <= j && nums[j] >= pivot)
                j--;  // 从右向左找首个小于基准值的元素
            if (i < j)
                swap(nums, i, j); // 交换这两个元素
        }
        swap(nums, i, right);  // 将基准值交换至分界线
        return i;              // 返回基准值的索引
    }


    // 哨兵划分: 以 nums[left] 为基准数
    public static int partition3(int[] nums, int left, int right) {

        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left])
                j--;          // 从右向左找首个小于基准数的元素
            while (i < j && nums[i] <= nums[left])
                i++;          // 从左向右找首个大于基准数的元素
            swap(nums, i, j); // 交换这两个元素
        }
        swap(nums, i, left);  // 将基准数交换至两子数组的分界线
        return i;             // 返回基准数的索引
    }

    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
